/*
    双指针：left在最左端，找零  right在最右端，找2
    i在(left, right]中遍历
    //如果 ni > nr，那么交换
    //如果 ni < nl，那么交换
    //如果 nl==0 && nr==2，说明这次left和right都已经找到，break，开启下一轮循环
    //如果 nl <= ni <= nr，i++, 继续寻找
*/
class Solution {
public:
    void sortColors(vector<int>& nums) {
          int left = 0, right = nums.size() - 1;
          while (left <= right)
          {
              int i = left + 1;
              while (i <= right)
              {
                  if (nums[i] > nums[right])
                      swap(nums[i], nums[right]);

                  if (nums[i] < nums[left])
                      swap(nums[i], nums[left]);
                  
                  if (nums[left] == 0 && [right] == 2)
                      break;

                  if (nums[i] >= nums[left] && nums[i] <= nums[right])
                      i++;
                  
              }
              left++;
              right--;
          }
    }
};